//给定一棵二叉树，设计一个算法，创建含有某一深度上所有节点的链表（比如，若一棵树的深度为 D，则会创建出 D 个链表）。返回一个包含所有深度的链表的数组。 
//
// 
//
// 示例： 
//
// 输入：[1,2,3,4,5,null,7,8]
//
//        1
//       /  \ 
//      2    3
//     / \    \ 
//    4   5    7
//   /
//  8
//
//输出：[[1],[2,3],[4,5,7],[8]]
// 
// Related Topics 树 广度优先搜索 链表 二叉树 
// 👍 54 👎 0

  
package com.zwy.leetcode.editor.cn;

import com.zwy.leetcode.ListNode;
import com.zwy.leetcode.TreeNode;


import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class ListOfDepthLcci{
    public static void main(String[] args) {
        Solution solution = new ListOfDepthLcci().new Solution();
//        [1,2,3,4,5,null,7,8]
        TreeNode arr=new TreeNode(1,new TreeNode(2,new TreeNode(4,new TreeNode(8),null),new TreeNode(5)),new TreeNode(3,null,new TreeNode(7)));
        solution.listOfDepth(arr);
      }
      //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode[] listOfDepth(TreeNode tree) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();

        ListNode []res=new ListNode[100];
        ListNode []res0=null;
        queue.add(tree);
        int high=0;
        while (!queue.isEmpty()){
            int size=queue.size();
            ListNode link=null;
            ListNode p=null;
            for (int i = 0; i < size; i++) {
                if(queue.peek().left!=null){
                    queue.add(queue.peek().left);
                }
                if(queue.peek().right!=null){
                    queue.add(queue.peek().right);
                }
                if(i==0){
                    link = new ListNode(queue.poll().val);
                    p=link;
                }

                else {
                    p.next=new ListNode(queue.poll().val);
                    p=p.next;
                }

            }
            res[high]=link;
            high++;
        }
        res0=new ListNode[high];
        for (int i = 0; i < high; i++) {
            res0[i]=res[i];
        }
        return res0;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}